This application claims priority under 35 U.S.C. xc2xa7119 of German No. DE 100 20 430.9, filed on Apr. 26, 2000.
1. Field of the Invention
The invention describes a method for the dynamic management of a read-write memory. Such read-write memories are used in practically all data processing systems. In the context of these memories, in particular random-access-memories (RAM), the difficulty exists that originally free memory will be filled successively by objects of different sizes. At first, the memory will be filled compactly, i.e., stored objects are created contiguously in memory using the available memory optimally. When single objects are then deleted, gaps are created in the memory. Basically, the originally filled memory is again writeable. Nevertheless, the memory is then fragmented. This means, the memory consists of used and free memory ranges of different sizes. The problem arises that often there is sufficient free memory available, but there is not sufficient free memory ranges available in the required size. The fraction of memory that is lost due this fragmentation can be significant.
2. The Prior Art
For an improved memory management, systems are available that provide memory compaction. E.g., methods are known that copy used memory into another memory space so that used storage is contiguous and space that becomes free becomes available as a contiguous free memory range as well.
Alternatively, methods are known that shift used memory so that a larger contiguous free memory range results.
With both of these above mentioned methods of memory management, the problem arises that used memory cells must be moved. Hence, it is required that all references for identification of certain memory cells must be readdressed. Usually, this is achieved by relatively complex referencing methods, with the result that accesses are slowed down. In any case, this results in higher load on the processor.
Another problem with the above mentioned methods is that moving of memory objects must be characterized as expensive. At these times, the memory is not available for use. The above mentioned solutions are hence not sufficient for the application in conjunction with real-time systems like industrial automation systems. In the current state-of-the-art there are approaches to solve this problem by moving memory in successive steps. Through this, memory should remain available for use. The problem arises that arrangements must be made for single applications to remain functional in conjunction with partially moved objects. In effect, this also results in slower memory access or a slower data processing system in general, respectively.
An alternative solution of the problem is to use a single size for storing all objects. This ensures that basically memory can be used in a compact way. The difficulty with this method is, that a significant amount of memory is used, since all objects are stored using a single size: the size that corresponds to the largest object that has to be presumed. Alternatively, subdividing all objects into smaller partial objects of equal size is conceivable. The general subdivision into partial objects in turn has the disadvantage, that essentially a reference management must be provided to link the partial blocks of the subdivided objects
The basis of the invention is to create a method for the management of a read-write memory that avoids the above mentioned disadvantages as much as possible and that enables an optimal memory usage with preferably invariable processor and memory performance.
The problem addressed by the invention is solved using a method for dynamic memory management in accordance with the main claim. In doing so, the basic idea of the invention is to associate a memory with a memory management system that masters several, at least two, different methods for storage and corresponding management. Accordingly, depending on the object that needs to be stored and the currently available state of the memory, the suitable storage method is chosen as appropriate. Normally, the storage method will be chosen depending on the size of the object that needs to be stored in relation to the size of the free memory ranges for each case. For this, the memory management system first regards memory generally as subdivided into partial blocks of equal size, while it discriminates depending on the above mentioned condition, whether an object that needs to be stored will be stored in contiguous blocks, hence contiguously, or distributedly.
In the case of storing an object in the form of distributed partial blocks, the partial blocks of this object will be equipped each with links such that all partial blocks of this object are connected through links. This is the so-called storage in the form of a graph.
Depending of the kind and size of the single objects a certain method of storage will be chosen. As an example, instances of classes could in any case be arranged distributedly.
In an advantageous implementation, a linked list of the single partial blocks is created, at least for a part of the objects that are stored distributedly.
To achieve the fastest possible memory access, it makes sense to use a tree structure in the case of distributed storage. In this case, the distributedly stored partial blocks will be linked in the form of a branched tree.
A further increase in efficiency of the memory management system in conjunction with these tree structures is achieved by assigning a root block to every tree that stores the substantial information on the form of a tree of a stored object, such as its size.
In an advantageous implementation an identification number for the branching depth of the tree is stored in the root block.
An enhanced memory management system results as well from assigning a memory flag to every partial block that contains the information whether the corresponding partial block is part of a contiguously stored object or a distributedly stored object. In the case that the memory management system distinguishes between two means of storing objects, this flag can be a single bit.
In an advantageous implementation this memory flag can be stored in an unused bit of the corresponding partial block. This saves memory space.
In conjunction with the above mentioned root blocks it makes sense for the root block to contain an identification number for the tree depth of the corresponding tree.
In doing so, the memory flag and the identification number for the branching depth of the tree can be combined reasonably into a single memory element within the partial block that forms the root block. Through this, the memory need will be reduced again.
In conjunction with the objects that are stored as contiguous block an additional linklist can be created. This linklist ensures that all partial blocks of an object are reachable through links from the first partial block. Through this, the memory management systems recognizes that the participating partial blocks are part of a common object.
Again in an advantageous implementation, the memory management system creates a bitvector with one bit corresponding to each partial block of the memory. In doing so, every bit of the bitvector contains information about whether two consecutive partial blocks are partial blocks of the same object.
In an alternative implementation an object flag can be assigned to every partial block. This flag indicates whether two consecutive partial blocks are constituents of the same object. In doing so, what has been said about the single bits of the bitvector is valid for the assignment of the object flags.